package com.algorithms.parsers;

import com.algorithms.linkedlists.LinkedStack;
import com.algorithms.utils.AlgorithmException;

/**
 * this Post-fix Parser uses Linked-Stack as a base
 * 
 * @author minhld
 *
 */
public class LinkedPostfixParser{
	
	/**
	 * convert a in-fix equation string into post-fix string
	 * <br>
	 * this will be the prerequisite step for equation 
	 * evaluating process
	 * 
	 * @param infixStr
	 * @return
	 */
	public static String parseInfix(String infixStr){
		String postFixStr = "";
		
		// clean all empty space in infix string
		infixStr = infixStr.replaceAll(" ", "");
		
		// operator stack
		LinkedStack<Character> operatorStack = new LinkedStack<>();
		
		try{
			char val;
			char peakOperator;
			for (int i = 0; i < infixStr.length(); i++){
				val = infixStr.charAt(i);
				switch (val){
					case '+' :
					case '-' :
					case '*' :
					case '/' : {
						if (operatorStack.isEmpty()){
							operatorStack.push(val);
							continue;
						}
						peakOperator = operatorStack.peak();
						
						if (peakOperator == '('){
							operatorStack.push(val);
						}else{
							if (getOperatorPriority(val) <= getOperatorPriority(peakOperator)){
								operatorStack.pop();
								postFixStr += peakOperator;
							}
							operatorStack.push(val);
						}
						break;
					}
					case '(' : {
						operatorStack.push(val);
						break;
					}
					case ')' : {
						while((peakOperator = operatorStack.pop()) != '('){
							postFixStr += peakOperator;
						}
						break;
					}
					default : {
						// write to output
						postFixStr += val;
						break;
					}
						
				}
			}
			
			while (!operatorStack.isEmpty()){
				peakOperator = operatorStack.pop();
				postFixStr += peakOperator;
			}
			
		}catch(AlgorithmException alEx){
			alEx.printStackTrace();
		}
		
		return postFixStr;
	}
	
	/**
	 * This function will evaluate a post-fix string and 
	 * give out the result in Integer format.
	 * <br><br>
	 * the operants should be 1-digit integers for better
	 * parsing and evaluating
	 * 
	 * @param postFixStr
	 * @return
	 */
	public static int evaluatePostfix(String postFixStr){
		int sum = 0;
		
		LinkedStack<Integer> sumStack = new LinkedStack<Integer>();
		
		try{
			char val;
			int intVal = 0;
			int oprant1 = 0, oprant2 = 0;
			for (int i = 0; i < postFixStr.length(); i++){
				val = postFixStr.charAt(i);
				
				if (!isOperator(val)){
					intVal = Integer.parseInt(Character.toString(val));
					sumStack.push(intVal);
				}else{
					oprant2 = sumStack.pop();
					oprant1 = sumStack.pop();
					sum = calculate(oprant1, oprant2, val);
					sumStack.push(sum);
				}
			}
		}catch(AlgorithmException alEx){
			alEx.printStackTrace();
		}
		
		return sum;
	}
	
	private static int calculate(int operant1, int operant2, 
									char operator){
		switch(operator){
			case '+' : {
				return operant1 + operant2;
			}
			case '-' : {
				return operant1 - operant2;
			}
			case '*' : {
				return operant1 * operant2;
			}
			case '/' : {
				return operant1 / operant2;
			}
			default : {
				return 0;
			}
		}
	}
	
	/**
	 * check if character is operator
	 * 
	 * @param val
	 * @return
	 */
	private static boolean isOperator(char val){
		return (val == '+' || val == '-' || val == '*' || val == '/');
	}
	
	/**
	 * get priority of operator
	 * 
	 * @param oper
	 * @return
	 */
	private static int getOperatorPriority(char oper){
		switch(oper){
			case '+' :
			case '-' : {
				return 1;
			}
			case '*' :
			case '/' : {
				return 2;
			}
			case '(' : {
				return 3;
			}
			default : {
				return 0;
			}
		}
	}
}
